1. Field of the Invention
The present invention relates to a high level synthesis apparatus and a high level synthesis method for synthesizing a circuit of a register transfer level or a gate level from a circuit described in a behavior level.
2. Related Background Art
With the recent trend toward a larger scale of LSIs, the circuits have been designed using high level synthesis in order to shorten the time required for LSI design. In the high level synthesis, a circuit of a register transfer level or a gate level is synthesized from a circuit represented in behavior description having a high level of abstraction, such as algorithm.
Meanwhile, in the circuit design in which the circuit is described in a register transfer level and the logic synthesis is performed based on this circuit description, megacells such as memory do not become a target of the logic synthesis. Therefore, when the megacells such as memory are to be used, a designer for the circuit has to make an instance description directly in the circuit description of the register transfer level.
On the other hand, behavior description is performed in the circuit design using high level synthesis, and therefore megacells can be described with variables such as array variables and structure variables. As a result, the variables can be allocated for memory element resources such as a memory, a register file or a register when the high level synthesis is carried out.
In the conventional high level synthesis, the techniques for allocating variables to registers and the like include, for example, to use the left edge algorithm that is explained in “HIGH-LEVEL SYNTHESIS, Introduction to Chip and System Design” (edited by Gajski, Wu, Dutt and Lin, published by Kluwer Academic Publishers, U.S. 1992). According to the technique using the left edge algorithm, first of all, scheduling is performed for determining a cycle for carrying out various operations in behavior description, and the lifetime of variables is analyzed.
Thereafter, the variables are sorted in the order of the lifetime and are allocated to registers in turn so as to avoid the overlapping of the lifetime. For instance, in the case where the variable is an array variable, the respective array elements of the array variable are allocated individually to the registers in accordance with the afore-mentioned technique.
Furthermore, in the conventional high level synthesis, techniques for allocating variables to memories include, for example, the technique in which a designer designates an array variable to be allocated to an arbitrary memory, whereby the array variable is allocated beforehand to the memory prior to the execution of the scheduling for determining the order of executing operations. For instance, in a high level synthesis apparatus disclosed in JP H05(1993)-101141 A, a designer of a circuit uses a command for memory allocation so as to allocate arbitrary array variables described in a behavior level circuit to arbitrary memories.
In the afore-mentioned technique for allocating array variables to memories, however, the scheduling follows the allocation of the array variables to the memories, and therefore the scheduling is performed under constraints based on the memory to which the allocation is designated. For that reason, in the case where the allocation of the array variable to the memory is not optimum, there occurs a problem of a failure to obtain the optimum scheduling result.
For example, in the case of the array variable using a structure variable written in the C language, in the description of the behavior level circuit, there is a case where reference is made with respect to the structure variable as a whole and there is another case where reference is made with respect to a member variable included in the structure. These cases have different bit widths for transferring data because of the difference in the referencing method therebetween.
Furthermore, in the high level synthesis according to JP H05(1993)-101141 A, when a structure variable is allocated to a memory, a bit width for the data transfer of the memory is limited to one type per each memory. Therefore, it is difficult to allocate a memory having the optimum bit width for the data transfer for both cases of the reference being made with respect to the structure variable as a whole and the reference being made with respect to member variables alone.
Moreover, the constraints on the bit width of the data transfer in the allocated memory cause the frequency of memory access when the reference is made with respect to the structure variable as a whole and the frequency of memory access when the reference is made with respect to the member variable alone to be determined.
Therefore, when the frequency of memory access affects the result of the scheduling, the optimum scheduling result would not be obtained. In order to cope with such a problem, the high level synthesis is required to select a memory that becomes a target of allocation so as to avoid the influence on the scheduling result or so as to obtain the optimum frequency.